package com.algorithm.dp;

/**
 * 01背包
 * 分割等和子集
 *
 * @author Amadeus
 * @date 2023/10/23
 */
public class canPartition {

    public static boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 > 0) {
            return false;
        }
        sum /= 2;
        int[] dp = new int[sum+1];
        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[j] == sum) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] ints = {1, 5, 11, 5};
        System.out.println(canPartition(ints));
    }

}
